def lcs_brute(shorter, longer):
    n = len(shorter)
    m = len(longer)
    if n > m:
        shorter, longer = longer, shorter
        n, m = m, n
    lcs = ''
    max_len = 0
    cnt = 0
    for i in range(m):
        for j in range(n):
            for k in range(n):    
                cnt += 1
                if longer[i:i + 1 + k] == shorter[j:j + 1 + k]:
                    xlen = len(longer[i:i + 1 + k])
                    if xlen > max_len:
                        max_len = xlen
                        lcs = longer[i:i + 1 + k]
    return lcs, cnt


def lcs_dynamic(shorter, longer):
    """
    程序使用了一个二维数组dp来存储子问题的解，
    其中dp[i][j]表示s1的前i个字符和s2的前j个字符的最长公共子串的长度。
    如果s1的第i个字符和s2的第j个字符相同，那么dp[i][j]就是dp[i-1][j-1] + 1；
    如果不同，那么dp[i][j]就是0。
    
    最后，程序根据dp数组中的最大值和对应的位置提取出最长公共子串。
    """
    n = len(shorter)
    m = len(longer)
    if n > m:
        shorter, longer = longer, shorter
        n, m = m, n
    end_pos = 0
    max_len = 0
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    cnt = 0
    for i in range(1, 1 + n):
        for j in range(1, 1 + m):
            cnt += 1
            if shorter[i - 1] == longer[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end_pos = i
                else:
                    dp[i][j] = 0
    lcs = shorter[end_pos - max_len:end_pos]
    return lcs, cnt


if '__main__' == __name__:
    str1 = 'BBBBBBBBBBBBBBBBBBBCMPLTRTOKBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB'
    str2 = 'AAAACMPLTRTOKAAAAAAAAAAAAAAAAAAAAAAAAA'
    r, c = lcs_brute(str1, 'X')
    print(f'|{r}|', c)
    r, c = lcs_brute(str1, str2)
    print(f'|{r}|', c)
    
    r, c = lcs_dynamic(str1, 'X')
    print(f'|{r}|', c)
    r, c = lcs_dynamic(str1, str2)
    print(f'|{r}|', c)
    